Search Results

Documents authored by Bafna, Mitali

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.20
Optimal Fine-Grained Hardness of Approximation of Linear Equations

Authors: Mitali Bafna and Nikhil Vyas

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system (A,b), for A ∈ ℝ^{n×n} and b ∈ ℝⁿ, we wish to find a vector x ∈ ℝⁿ such that Ax = b. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time O(n^ω). We consider the problem of finding ε-approximate solutions to linear systems with respect to the L₂-norm, that is, given a satisfiable linear system (A ∈ ℝ^{n×n}, b ∈ ℝⁿ), find an x ∈ ℝⁿ such that ||Ax - b||₂ ≤ ε||b||₂. Our main result is a fine-grained reduction from computing the rank of a matrix to finding ε-approximate solutions to linear systems. In particular, if the best known Õ(n^ω) time algorithm for computing the rank of n × O(n) matrices is optimal (which we conjecture is true), then finding an ε-approximate solution to a dense linear system also requires Ω̃(n^ω) time, even for ε as large as (1 - 1/poly(n)). We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices and well-conditioned linear systems. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
Cite as

Mitali Bafna and Nikhil Vyas. Optimal Fine-Grained Hardness of Approximation of Linear Equations. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.ICALP.2021.20,
  author =	{Bafna, Mitali and Vyas, Nikhil},
  title =	{{Optimal Fine-Grained Hardness of Approximation of Linear Equations}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.20},
  URN =		{urn:nbn:de:0030-drops-140894},
  doi =		{10.4230/LIPIcs.ICALP.2021.20},
  annote =	{Keywords: Linear Equations, Fine-Grained Complexity, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.32
Imperfect Gaps in Gap-ETH and PCPs

Authors: Mitali Bafna and Nikhil Vyas

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a way to transform a PCP with imperfect completeness to one with perfect completeness, when the initial gap is a constant. We show that PCP_{c,s}[r,q] subseteq PCP_{1,s'}[r+O(1),q+O(r)] for c-s=Omega(1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NP with a O(log n) additive loss in the query complexity q. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs, (when completeness is not 1) analogous to questions studied in parallel repetition [Anup Rao, 2011] and pseudorandomness [David Gillman, 1998] and might be of independent interest. We also investigate the time-complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. MAX 3SAT(1-epsilon,1-delta), delta > epsilon has 2^{o(n)} algorithms if and only if MAX 3SAT(1,1-delta) has 2^{o(n)} algorithms. We also relate the time complexities of these two problems in a more fine-grained way to show that T_2(n) <= T_1(n(log log n)^{O(1)}), where T_1(n),T_2(n) denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness respectively.
Cite as

Mitali Bafna and Nikhil Vyas. Imperfect Gaps in Gap-ETH and PCPs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.CCC.2019.32,
  author =	{Bafna, Mitali and Vyas, Nikhil},
  title =	{{Imperfect Gaps in Gap-ETH and PCPs}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.32},
  URN =		{urn:nbn:de:0030-drops-108545},
  doi =		{10.4230/LIPIcs.CCC.2019.32},
  annote =	{Keywords: PCP, Gap-ETH, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.16
On the Sensitivity Conjecture for Read-k Formulas

Authors: Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over R, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the "missing link". Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and functions describing graph properties. In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.
Cite as

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.MFCS.2016.16,
  author =	{Bafna, Mitali and Lokam, Satyanarayana V. and Tavenas, S\'{e}bastien and Velingker, Ameya},
  title =	{{On the Sensitivity Conjecture for Read-k Formulas}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16},
  URN =		{urn:nbn:de:0030-drops-64317},
  doi =		{10.4230/LIPIcs.MFCS.2016.16},
  annote =	{Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact